package LC;

/**
 * https://leetcode.com/problems/sort-list/description/
 * Sort a linked list in O(n log n) time using constant space complexity.
 */
public class LC_148_SortList_LinkedList_Sort {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(3);
        head.next.next = new ListNode(2);
        ListNode h1 = Solution.sortList(head);
        ListNode cur = h1;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    static class Solution {
        static ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            ListNode middle = getMiddleOfList(head);
            ListNode next = middle.next;
            middle.next = null;
            return mergeTwoList(sortList(head), sortList(next));
        }

        private static ListNode mergeTwoList(ListNode headA, ListNode headB) {
            ListNode fakeNode = new ListNode(-1);
            ListNode cur = fakeNode;
            while (headA != null && headB != null) {
                if (headA.val <= headB.val) {
                    cur.next = headA;
                    headA = headA.next;
                } else {
                    cur.next = headB;
                    headB = headB.next;
                }
                cur = cur.next;
            }
            cur.next = headA == null ? headB : headA;
            return fakeNode.next;
        }

        private static ListNode getMiddleOfList(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

}